package com.lw.leetcode.dp.c;

/**
 * Created with IntelliJ IDEA.
 * 600. 不含连续1的非负整数
 *
 * @author liw
 * @version 1.0
 * @date 2021/9/14 9:44
 */
public class FindIntegers {

    public static void main(String[] args) {
        FindIntegers test = new FindIntegers();

        // 5
//        int n = 5;

        // 8
//        int n = 10;

        // 8
//        int n = 14;

        // 21
        int n = 46;

        int integers = test.findIntegers(n);
        System.out.println(integers);


        for (int i = 50000; i < 50000000; i++) {
            int aa = test.findIntegers(n);
            int bb = test.findIntegers2(n);
            if (aa != bb) {
                System.out.println(i);
            }
        }


        System.out.println("OK");
    }

    public int findIntegers(int n) {
        int[] arr = new int[32];
        int[] values = new int[32];
        int item = n;
        int i = 2;
        arr[0] = 1;
        arr[1] = 2;
        values[1] = item & 1;
        item >>= 1;
        while (item != 0) {
            arr[i] = arr[i - 1] + arr[i - 2];
            values[i] = item & 1;
            item >>= 1;
            i++;
        }
        int sum = arr[i - 2];
        for (int j = i - 2; j >= 0; j--) {
            if (values[j] == 1) {
                if (values[j + 1] == 1) {
                    sum += arr[j - 1] - 1;
                    break;
                } else {
                    sum += arr[j - 1];
                }
            }
        }
        return sum + 1;
    }


    public int findIntegers2(int n) {
        int[] dp = new int[31];
        dp[0] = dp[1] = 1;
        for (int i = 2; i < 31; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        int pre = 0, res = 0;
        for (int i = 29; i >= 0; --i) {
            int val = 1 << i;
            if ((n & val) != 0) {
                res += dp[i + 1];
                if (pre == 1) {
                    break;
                }
                pre = 1;
            } else {
                pre = 0;
            }

            if (i == 0) {
                ++res;
            }
        }

        return res;
    }


}
